package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.ArrayProblem;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode.com/problems/find-the-duplicate-number/
 * Given an array of integers nums containing n + 1 integers
 * where each integer is in the range [1, n] inclusive.
 * There is only one duplicate number in nums, return this duplicate number.<p>
 * <p>
 * 这个问题数组可类比为链表, 问题就被类比为判断链表是否有环及环的入口.
 * Floyd's Tortoise and Hare (Cycle Detection)
 * <p>
 * LC448
 * LC142
 *
 * @author tzp
 * @since 2020/9/16
 */
public class LC287 implements ArrayProblem {
    public int findDuplicate(int[] nums) {
        //hashset的方法最呆了
        Set<Integer> seen = new HashSet<Integer>();
        for (int num : nums) {
            if (seen.contains(num)) {
                return num;
            }
            seen.add(num);
        }

        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new LC287().findDuplicate(new int[]{1, 2, 1}));
        System.out.println(new LC287().findDuplicate(new int[]{2, 2, 2, 2, 2}));
    }
}
